#include <iostream>
#include <vector>

using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    vector<int> nextArrayConstruction(vector<int> &pattern)
    {
        int n = pattern.size();
        if (n == 1)
        {
            return {-1};
        }
        vector<int> next(n, -1);
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < n)
        {
            if (pattern[i - 1] == pattern[cn])
            {
                next[i++] = ++cn;
            }
            else if (cn > 0)
            {
                cn = next[cn];
            }
            else
            {
                next[i++] = 0;
            }
        }
        return next;
    }
    bool findRet(vector<int> &pattern, vector<int> &next, TreeNode *cur, int index)
    {
        if(index >= pattern.size()){
            return true;
        }
        if(cur == nullptr){
            return false;
        }

       while(index >= 0 && cur->val != pattern[index]){
           index = next[index];
       }

       return findRet(pattern, next, cur->left, index + 1) || findRet(pattern, next, cur->right, index + 1);
    }
    bool isSubPath(ListNode *head, TreeNode *root)
    {
        // 1.收集
        vector<int> pattern;
        while (head != nullptr)
        {
            pattern.push_back(head->val);
            head = head->next;
        }
        // 2.构建next数组
        vector<int> next = nextArrayConstruction(pattern);
        // 3.遍历树，返回结果
        return findRet(pattern, next, root, 0);
    }
};

int main()
{
    return 0;
}